#include "heapsort.hpp" /

// 交换两个整数的值
void swap(int &num1, int &num2)
{
    int tempt = num1;
    num1 = num2;
    num2 = tempt;
}

// 向上调整堆，确保以child为根的子树满足最大堆的性质
void AdjustUp(int *arry, int size, int child)
{
    int parent = (child - 1) / 2; // 计算父节点的索引
    while (child > 0 && arry[child] > arry[parent]) // 当child不是根节点且子节点的值大于父节点的值时
    {
        swap(arry[child], arry[parent]); // 交换子节点和父节点的值
        child = parent; // 更新child为当前父节点的位置
        parent = (child - 1) / 2; // 更新父节点为新的父节点的位置
    }
}

// 向下调整堆，确保以pos为根的子树满足最大堆的性质
void AdjustDown(int *arry, int size, int pos)
{
    int parent = pos; // 从给定的位置开始
    int child = parent * 2 + 1; // 左子节点的索引
    while (child < size) // 当存在左子节点时
    {
        // 如果存在右子节点且右子节点的值大于左子节点的值
        if (child < size - 1 && arry[child] < arry[child + 1])
        {
            ++child; // 选择右子节点作为较大的子节点
        }
        // 如果父节点的值小于较大的子节点的值
        if (arry[parent] < arry[child])
        {
            swap(arry[child], arry[parent]); // 交换父节点和较大的子节点
            parent = child; // 更新父节点为当前子节点的位置
            child = parent * 2 + 1; // 更新子节点索引为新的左子节点
        }
        else
            break; // 如果父节点的值不小于子节点的值，则堆已满足性质，退出循环
    }
}

// 堆排序算法
void HeapSort(int* arry, int size)
{
    // 构建最大堆
    int n = size - 1; // 最后一个非叶子节点的索引
    for (int i = (n - 1) / 2; i >= 0; --i) // 从最后一个非叶子节点开始向上遍历
    {
        AdjustDown(arry, size, i); // 调整每个子树，使其满足最大堆的性质
    }

    // 排序过程
    for (int i = n; i >= 0; --i) // 从最后一个元素开始向前遍历
    {
        swap(arry[0], arry[i]); // 将当前堆的最大元素（根节点）与末尾元素交换
        AdjustDown(arry, i, 0); // 调整剩余的元素，使其重新满足最大堆的性质
    }
}